//
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class SentenceDecomposition
{
	public final static int mmax = 1000000000;
	public Integer dp[];
	public String str;
	public String[] list;

	public int decompose(String sentence, String[] validWords)
	{
		str = sentence;
		list = validWords;
		dp = new Integer[str.length() + 1];
		int ret = solve(str.length());
		return ret==mmax? -1 : ret;
	}

	public int solve(int len){
		if(dp[len] != null) return dp[len];
		dp[len] = mmax;
		if(len == 0){
			return dp[len] = 0;
		}
		for(String s: list){
			int len2 = s.length();
			if(len2 > len) continue;
			int cost = match(s, str.substring(len-len2, len));
			if(cost == -1) continue;
			dp[len] = Math.min(dp[len], cost + solve(len-len2));
		}
		return dp[len];
	}

	public int match(String a, String b){
		String c = sorted(a);
		String d = sorted(b);
		if(c.compareTo(d) != 0) return -1;
		int ret = 0;
		for(int i=0; i<a.length(); i++){
			if(a.charAt(i) != b.charAt(i))
				ret++;
		}
		return ret;
	}

	public String sorted(String a){
		char[] content = a.toCharArray();
		Arrays.sort(content);
		String ret = new String(content);
		return ret;
	}
	
	
}
//Powered by [KawigiEdit] 2.0!
